#include <iostream>
#include <cstdlib>
#include "CppDArray.h"

//构造函数
DynamicArray::DynamicArray(void(*CLearptr)(ElementType))
{
    this->dp = NULL;
    this->size = 0;
    this->len = 0;
    this->CLearptr = CLearptr;
}

//析构函数
DynamicArray::~DynamicArray()
{
    if(this->CLearptr != NULL)
    {
        for(int i=0;i<this->len;i++)
        {
            CLearptr(this->dp[i]);
        }
    }
    delete this->dp;
    this->size = 0;
    this->len = 0;
}

//尾插
bool DynamicArray::InsertArrayTail(ElementType element)
{
    if(this->dp==NULL)
    {
        this->size = (this->size+1)*2;
        this->dp = new ElementType[this->size];
    }
    else if(this->len > this->size)
    {
        int newsize = (this->size+1)*2;
        ElementType* newarray = new ElementType[newsize];
        for(int i=0;i<this->len;i++)
        {
            newarray[i] = this->dp[i];
        }
        delete []dp;
        /*指向新的变量*/
        this->dp = newarray;
        this->size = newsize;
    }
    this->dp[this->len++] = element;
    return true;
}

//按位置删
bool DynamicArray::RemoveByIndex(int index)
{
    if(index<0||index>=this->len)
    {
        std::cout<<"invalid index positon!"<<std::endl;
        return false;
    }
    if(this->CLearptr!=NULL)
    {
        CLearptr(this->dp[index]);
    }
    for(int i=index;i<this->len-1;i++)
    {
        this->dp[i] = this->dp[i+1];
    }
    this->len--;
    return true;
}

//打印
void DynamicArray::DisplayDynamicArray(void(*Printptr)(ElementType))
{
    for(int i=0;i<this->len;i++)
    {
        Printptr(this->dp[i]);
    }
    std::cout<<std::endl;
}

//按值删
bool DynamicArray::RemoveArray_ByElement(ElementType element,bool(*Compareptr)(ElementType,ElementType))
{
    for(int i=0;i<this->len;i++)
    {
        if(Compareptr(element,this->dp[i])==true)
        {
            if(RemoveByIndex(i)==false)
            {
                return false;
            }
            i--;
        }
    }
    return true;
}

/*快速排序*/
void fastsort(ElementType* s,int start,int end,bool(*Compareptr)(ElementType,ElementType))
{
    if(start>end)
    {
        return;
    }
    int left=start;
    int right= end;
    ElementType temp = s[left];
    while(left<right)
    {
        while(left<right&&Compareptr(s[right],temp)==true)
        {
            right--;
        }
        if(left<right)
        {
            s[left]=s[right];
            left++;
        }
        while(left<right&&Compareptr(s[left],temp)==false)
        {
            left++;
        }
        if(left<right)
        {
            s[right] = s[left];
            right--;
        }
        s[left]=temp;
    }
    fastsort(s,start,left-1,Compareptr);
    fastsort(s,right+1,end,Compareptr);
}


void DynamicArray::Sort(bool(*Compareptr)(ElementType,ElementType))
{
    fastsort(this->dp,0,this->len-1,Compareptr);
}

DynamicArray DynamicArray::FindByElement(ElementType element,bool(*funcptr)(ElementType,ElementType))
{
    DynamicArray result(NULL);
    for(int i=0;i<this->len;i++)
    {
        if(funcptr(element,this->dp[i])==true)
        {
            result.InsertArrayTail(this->dp[i]);
        }
    }
    return result;
}

bool DynamicArray::RemoveFirstArray_ByElement(ElementType element,bool(*Compareptr)(ElementType,ElementType))
{
    for(int i=0;i<this->len;i++)
    {
        if(Compareptr(element,this->dp[i])==true)
        {
            if(RemoveByIndex(i)==false)
            {
                return false;
            }
            return true;
        }
    }
    return true;
}



